﻿/*
 * @autor: hectorea
 * @date: 24/07/2012
 * @project: LinkedList
 */

using System;
using System.Collections;

namespace LinkedList
{    
    public class LinkedList
    {                
        public Node Head { get; set; }

        public int Count { get; private set; }      

        public LinkedList()
        {
            this.Head = null;
            this.Count = 0;
        }                 
       
        private Node FindNext(int data)
        {
            Node current = new Node();
            current = Head;

            while (current != null && !(current.Data.Equals(data)))
                current = current.Next;
            return current;
        }

        private Node FindPrevious(int data)
        {
            Node current = new Node();
            current = this.Head;

            if (current != null && current.Data == data)
                return null;

            while (current.Next != null && !(current.Next.Data == data))
                current = current.Next;

            return current;
        }
        
        public void AddFirst(int data)
        {
            Node newNode = new Node(data);

            if (this.Head != null)
            {
                newNode.Next = this.Head;
                this.Head = newNode;
            }
            else
            {
                this.Head = newNode;
            }

            this.Count++;
        }

        public void AddLast(int data)
        {
            Node newNode = new Node(data);

            if (this.Head != null)
            {
                Node current = this.Head;

                while (current.Next != null)
                    current = current.Next;

                current.Next = newNode;
            }
            else
            {
                this.Head = newNode;
            }

            this.Count++;
        }
        
        public void InsertAfter(int data, int after)
        {
            Node current = FindNext(after);

            Node newNode = new Node(data);
            
            newNode.Next = current.Next;
            current.Next = newNode;
        }

        public void InsertBefore(int data, int before)
        {            
            Node current = FindPrevious(before);
            Node newNode = new Node(data);

            if (current == null)
            {
                newNode.Next = this.Head;
                this.Head = newNode;
            }
            else
            {
                newNode.Next = current.Next;
                current.Next = newNode;
            }
            
          
        }

        public void Remove(int data)
        {
            Node previous = FindPrevious(data);

            if (previous.Next != null)
                previous.Next = previous.Next.Next;
        }

        public Node Remove(int data, Node current)
        {
            if (data == null)
                return Head;
            if (current == null ||current.Next == null)
                return current;

            if (current.Data.Equals(data))
            {
                return Remove(data, current.Next);
            }
            else
            {         
                current.Next = Remove(data, current.Next);                
                return current;
            }            
        }

        public void RemoveFirst()
        {
            if (Head != null)
            {
                Node current = Head.Next;
                Head = current;
            }
        }

        public void RemoveLast()
        {
            if (Head != null)
            {
                Node current = Head;

                while (current.Next != null && current.Next.Next != null)
                    current = current.Next;

                current.Next = null;
            }
        }

        public void Clear()
        {
            Head = null;
        }

        public void FindNTh(int nthposition)
        {
            if (this.Head == null)
                Console.WriteLine("Linked List Empty");

            //Point both to the begining of the list
            Node nth = this.Head;
            Node iterator = this.Head;

            //Iterate until the position N
            //Now we have a gap between the nth and iterator of N position
            for (int i = 0; i < nthposition; i++)
            {
                if (iterator != null)
                {
                    iterator = iterator.Next;
                }
                else
                {
                    Console.WriteLine("The list has ended");
                    return;
                }
            }

            //Finally, we iterate until the end of the LinkedList
            //When iterator reaches the end, nth will be positioned in the node we want to get
            while (iterator != null)
            {
                nth = nth.Next;
                iterator = iterator.Next;
            }
            //Display the current status of the LinkedList
            Display();
            Console.WriteLine(string.Format("The NTh element is {0}", nth.Data));
        }

        public void Reverse()
        {
            if (Head == null)
                return;

            Node previous = null;
            Node current = Head;
            Node next = null;

            while (current != null)
            {
                next = current.Next;
                current.Next = previous;
                previous = current;
                current = next;
            }

            this.Head = previous;
        }

        public void Reverse(Node current)
        {
            if (current == null || current.Next == null)
            {
                this.Head = current;
                return;
            }

            Reverse(current.Next);

            Node temp = current.Next;
            current.Next = null;
            temp.Next = current;
        }

        public bool HasLoop()
        {
            Node tortoise = Head;
            Node hare = Head;

            while (tortoise != null && hare != null && hare.Next != null)
            {
                tortoise = tortoise.Next;
                hare = hare.Next.Next;

                if (tortoise == hare)
                    return true;
            }

            return false;
        }

        public void Partition(int pivot)
        {
            Node current = this.Head;
            Node lesser = null;
            Node greater = null;

            while (current != null)
            {
                Node temp = new Node(current.Data);

                if ( int.Parse(current.Data.ToString()) < pivot)
                {
                    if (lesser != null)
                        temp.Next = lesser;

                    lesser = temp;
                }
                else
                {
                    if (greater != null)
                        temp.Next = greater;

                    greater = temp;
                }

                current = current.Next;
            }

            this.Head = lesser;
            while (lesser.Next != null)
                lesser = lesser.Next;

            lesser.Next = greater;
        }

        public void GetDistinctValues()
        {
            if (this.Head == null)
                return;

            Node current = this.Head;
            Hashtable ht = new Hashtable();

            while (current != null)
            {
                var key = current.Data;
                if (ht.ContainsKey(key))
                {
                    var value = ht[key];
                    ht[key] = int.Parse(value.ToString()) + 1;
                }
                else
                {
                    ht.Add(key, 1);
                }

                current = current.Next;
            }

            this.Head = null;

            foreach (DictionaryEntry entry in ht)
            {
                if (int.Parse(entry.Value.ToString()) == 1)
                {
                    AddFirst((int)entry.Key);
                }
            }
        }

        public void RemoveDuplicates()
        {
            if (this.Head == null)
                return;

            Node current = this.Head;

            while (current != null)
            {
                Node scout = current;

                while (scout.Next != null)
                {
                    if (scout.Next.Data.Equals(current.Data))
                    {
                        scout.Next = scout.Next.Next;
                    }
                    else
                    {
                        scout = scout.Next;
                    }
                }

                current = current.Next;
            }

        }


        /// <summary>
        /// Print the nodes of the LinkedList
        /// </summary>
        /// <param name="HasBreakLine">True if you want to see the previous status of the LinkedList</param>
        public void Display()
        {
            Node node = this.Head;

            while (node != null)
            {
                Console.Write(string.Format("|{0}||->", node.Data));
                node = node.Next;
            }

            Console.ReadLine();
        }
        
    }

    /// <summary>
    /// Each record of a linked list is often called an element or node.
    /// 
    /// The field of each node that contains the address of the next node is usually called the next link or next pointer. The remaining fields are 
    /// known as the data, information, value, cargo, or payload fields.
    /// 
    /// The head of a list is its first node. The tail of a list may refer either to the rest of the list after the head, or to the last node in the 
    /// list. 
    ///     
    /// </summary>
    public class Node
    {                      
        public int Data { get; set; }        
        public Node Next { get; set; }
               
        public Node()
        {
            this.Next = null;
        }
        public Node(int data)
        {
            this.Data = data;
        }
    }
}
